package com.myc.subjects.array;

/**
 * LeetCode题号：48
 *
 * 旋转图像
 *
 * 给定一个 n×n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
 *
 * 你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
 *
 * 示例 1：
 * 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
 * 输出：[[7,4,1],[8,5,2],[9,6,3]]
 *
 * 示例 2：
 * 输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
 * 输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
 *
 * 示例 3：
 * 输入：matrix = [[1]]
 * 输出：[[1]]
 *
 * 示例 4：
 * 输入：matrix = [[1,2],[3,4]]
 * 输出：[[3,1],[4,2]]
 *
 * 提示：
 * matrix.length == n
 * matrix[i].length == n
 * 1 <= n <= 20
 * -1000 <= matrix[i][j] <= 1000
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/rotate-image
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class Xuanzhuantuxiang {
    public static void main(String[] args){
        Xuanzhuantuxiang xuanzhuantuxiang = new Xuanzhuantuxiang();
        int[][] matrix1 = {{1,2,3},{4,5,6},{7,8,9}};
        int[][] matrix2 = {{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}};
        xuanzhuantuxiang.printMatrix(matrix1);
        xuanzhuantuxiang.rotate3(matrix1);
        xuanzhuantuxiang.printMatrix(matrix1);
        xuanzhuantuxiang.printMatrix(matrix2);
        xuanzhuantuxiang.rotate3(matrix2);
        xuanzhuantuxiang.printMatrix(matrix2);
    }

    /**
     * 方法一：数学方法（先转置再左右翻转）
     * 时间复杂度：O(n^2)
     * 使用数学方法先沿着左上到右下的对角线转置二维矩阵，再左右翻转矩阵
     */
    public void rotate1(int[][] matrix) {
        int n = matrix.length;

        //沿着对角线转置矩阵
        for(int i = 0; i < n; i++){
            for(int j = 0; j < i; j++){//这里可以选择上半部分或者下半部分，如果选上半部分则是for(int j = i; j < n; j++)
                //交换每个对称位置上的值
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }

        //矩阵左右翻转
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n/2; j++){//这里仅仅需要遍历一半的长度即可
                //交换对称位置上的值
                int temp = matrix[i][n - j - 1];
                matrix[i][n - j - 1] = matrix[i][j];
                matrix[i][j] = temp;
            }
        }
    }

    /**
     * 分治思想
     * 时间复杂度：O(n^2)
     * 将原矩阵拆分为四部分分别进行旋转
     */
    public void rotate2(int[][] matrix){
        int n = matrix.length;
        for(int i = 0; i < n / 2 + n % 2; i++){//这里注意：如果矩阵的边长是奇数，要么行加上中间的那列数，要么列加上中间那行数，这里我选择了列加上中间那行
           for(int j = 0; j < n / 2; j++){
                int row = i;
                int col = j;
                int[] temp = new int[4];//定义长度为4的数组，分别存放一次旋转，对应的四个位置的数据
                for(int k = 0; k < 4; k++){
                    temp[k] = matrix[row][col];
                    int t = row;
                    row = col;//旋转之后的行等于旋转之前的列
                    col = n - t - 1;//旋转之前的行 + 旋转之后的列 = n - 1
                }
                //对于4个位置上的值进行旋转
                for(int k = 0; k < 4; k++){
                    matrix[row][col] = temp[(k + 3)%4];//这里的数学小技巧可以求出上一个temp的值
                    int t = row;
                    row = col;
                    col = n - t - 1;
                }
           }
        }
    }

    /**
     * 方法三：方法二改进
     * 时间复杂度：O(n^2)
     * 在方法二的基础上将temp缩减为存一个值，然而我在LeetCode上测试结果内存消耗居然比方法二要大...这是为什么？
     */
    public void rotate3(int[][] matrix){
        int n = matrix.length;
        for(int i = 0; i < (n + 1) / 2; i++){//这种方式也可以使列加上中间那行
            for(int j = 0; j < n / 2; j++){
                int temp = matrix[i][j];//temp存入第一个值

                //四步旋转
                matrix[i][j] = matrix[n - j - 1][i];
                matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
                matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
                matrix[j][n - i - 1] = temp;
            }
        }
    }

    //打印矩阵方法
    public void printMatrix(int[][] matrix){
        System.out.println("matrix:");
        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix[i].length; j++){
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }
    }

    //官方题解
    //方法一：使用辅助数组
    public void rotateOfficial1(int[][] matrix) {
        int n = matrix.length;
        int[][] matrix_new = new int[n][n];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                matrix_new[j][n - i - 1] = matrix[i][j];
            }
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                matrix[i][j] = matrix_new[i][j];
            }
        }
    }

    //方法二：原地旋转
    public void rotateOfficial2(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < (n + 1) / 2; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - j - 1][i];
                matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
                matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
                matrix[j][n - i - 1] = temp;
            }
        }
    }

    //方法三：用翻转代替旋转
    public void rotateOfficial3(int[][] matrix) {
        int n = matrix.length;
        // 水平翻转
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < n; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - i - 1][j];
                matrix[n - i - 1][j] = temp;
            }
        }
        // 主对角线翻转
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
    }

}

/**
 * 总结：
 * 技巧：
 * 1.数学方法小技巧求得数组上一个值而不会使下标成为负数
 * 2.使用翻转代替旋转
 * 3.找出下标对应关系原地旋转
 *
 * 问题：
 * 为什么方法三内存消耗大于方法二？
 */
